package zuochengyun;

//数组排序之后相邻数的最大差值
public class MaxSubAfterSort {

	
	public static void main(String[] args) {
		int[] array = {9, 3, 1, 10, 15};
		int[] array2 = {2, -9, 3, 5, 12};
		MaxSubAfterSort object = new MaxSubAfterSort();
		object.maxGap(array);
		object.maxGap(array2);
	}
	
	public int maxGap(int[] nums){
		if(nums == null || nums.length < 2){
			return 0;
		}
		int len = nums.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			min = Math.min(min, nums[i]);
			max = Math.max(max, nums[i]);
		}
		//如果相等，那么说明都是一样的，返回0即可
		if(min == max){
			return 0;
		}
		//核心思想是通过桶排序来完成，如果长度为N，那么建立N + 1个桶，将max放在N+1的桶中
		//然后每个桶负责的区间大小为max - min / N
		//那么如果一个数为num，它应该分配在(num - min) * len / (max - min)号桶里
		boolean[] hasNum = new boolean[len + 1];
		
		//由于每个桶的间距不会超过桶的区间，而且由于有N + 1个桶，所以一定会有空桶，空桶之间的间隔一定会比较大
		//所以我们只需要比较桶之间的间距即可，所以要记录各个桶的最大值和最小值
		int[] maxs = new int[len + 1];	//记录桶的最大值
		int[] mins = new int[len + 1];	//记录桶的最小值
		int bucketId = 0;
		for (int i = 0; i < len; i++) {
			bucketId = bucket(nums[i], len, min, max);
			mins[bucketId] = hasNum[bucketId] ? Math.min(mins[bucketId], nums[i]) : nums[i];
			maxs[bucketId] = hasNum[bucketId] ? Math.max(maxs[bucketId], nums[i]) : nums[i];
			hasNum[bucketId] = true;
		}
		int res = 0;
		int lastMax = 0;
		int i = 0;
		
		//因为min肯定在1号桶里面，那么这一段代码是什么意思呢
		while(i <= len){
			if(hasNum[i++]){	//找到第一个不为空的桶
				lastMax = maxs[i - 1];
				System.out.println("the current " + i);
				break;
			}
		}
		
		for (; i < mins.length; i++) {
			if(hasNum[i]){
				res = Math.max(res, mins[i] - lastMax);
				lastMax = maxs[i];
			}
		}
		return res;
	}

	//为每个数分配桶的编号，注意，首先乘的话有可能溢出
	public int bucket(long num, long len, long min, long max) {
		return (int) ( (num - min) * len / (max - min));
	}
	
}
